from collections import deque

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y - 1),
    lambda x, y: (x, y + 1),
]


def print_r(path):
    real_path = []
    i = len(path) - 1
    while i >= 0:
        real_path.append(path[i][:2])
        i = path[i][2]
    real_path.reverse()
    for node in real_path:
        print(node, end='->')
    print('\b\b')


def maze_path_queue(x1, y1, x2, y2):
    queue = deque()
    path = []
    queue.append((x1, y1, -1))
    while len(queue) > 0:
        # 队列不空时循环
        cur_node = queue.popleft()
        path.append(cur_node)
        if cur_node[0] == x2 and cur_node[1] == y2:
            # 到达终点
            print_r(path)
            return True

        for dir in dirs:
            next_node = dir(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                queue.append((next_node[0], next_node[1], len(path) - 1))
                # 标记为已经走过
                maze[next_node[0]][next_node[1]] = 2
    else:
        return False


maze_path_queue(1, 1, 8, 8)
# (1, 1)->(2, 1)->(3, 1)->(4, 1)->(5, 1)->(5, 2)->(5, 3)->(6, 3)->(6, 4)->(6, 5)->(7, 5)->(8, 5)->(8, 6)->(8, 7)->(8, 8)